package newShiyan4;

import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉排序树类
 * 实现二叉排序树的创建、查找、插入、删除以及各种遍历操作
 */
public class BinarySearchTree {
    private TreeNode root; // 根结点

    /**
     * 构造函数，创建空的二叉排序树
     */
    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * 获取根结点
     * 
     * @return 根结点引用
     */
    public TreeNode getRoot() {
        return root;
    }

    /**
     * 判断树是否为空
     * 
     * @return 如果树为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 查找元素（递归方式）
     * 
     * @param data 要查找的整数
     * @return 如果找到返回true，否则返回false
     */
    public boolean search(int data) {
        return searchRecursive(root, data);
    }

    /**
     * 递归查找辅助方法
     * 
     * @param node 当前结点
     * @param data 要查找的数据
     * @return 如果找到返回true，否则返回false
     */
    private boolean searchRecursive(TreeNode node, int data) {
        if (node == null) {
            return false;
        }
        if (data == node.data) {
            return true;
        } else if (data < node.data) {
            return searchRecursive(node.left, data);
        } else {
            return searchRecursive(node.right, data);
        }
    }

    /**
     * 插入元素（递归方式）
     * 
     * @param data 要插入的整数
     */
    public void insert(int data) {
        root = insertRecursive(root, data);
    }

    /**
     * 递归插入辅助方法
     * 
     * @param node 当前结点
     * @param data 要插入的数据
     * @return 插入后的根结点
     */
    private TreeNode insertRecursive(TreeNode node, int data) {
        if (node == null) {
            return new TreeNode(data);
        }
        if (data < node.data) {
            node.left = insertRecursive(node.left, data);
        } else if (data > node.data) {
            node.right = insertRecursive(node.right, data);
        }
        // 如果data == node.data，不插入（二叉排序树不允许重复）
        return node;
    }

    /**
     * 删除元素
     * 
     * @param data 要删除的整数
     * @return 如果删除成功返回true，否则返回false
     */
    public boolean delete(int data) {
        if (!search(data)) {
            return false; // 元素不存在
        }
        root = deleteRecursive(root, data);
        return true;
    }

    /**
     * 递归删除辅助方法
     * 
     * @param node 当前结点
     * @param data 要删除的数据
     * @return 删除后的根结点
     */
    private TreeNode deleteRecursive(TreeNode node, int data) {
        if (node == null) {
            return null;
        }
        if (data < node.data) {
            node.left = deleteRecursive(node.left, data);
        } else if (data > node.data) {
            node.right = deleteRecursive(node.right, data);
        } else {
            // 找到要删除的结点
            // 情况1：没有子结点或只有一个子结点
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }
            // 情况2：有两个子结点，找到右子树的最小值（或左子树的最大值）
            node.data = findMin(node.right);
            node.right = deleteRecursive(node.right, node.data);
        }
        return node;
    }

    /**
     * 找到以node为根的子树中的最小值
     * 
     * @param node 根结点
     * @return 最小值
     */
    private int findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node.data;
    }

    /**
     * 前序遍历（递归方式）
     */
    public void preOrderRecursive() {
        System.out.print("前序遍历（递归）：");
        preOrderRecursive(root);
        System.out.println();
    }

    /**
     * 前序遍历递归辅助方法
     * 
     * @param node 当前结点
     */
    private void preOrderRecursive(TreeNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrderRecursive(node.left);
            preOrderRecursive(node.right);
        }
    }

    /**
     * 前序遍历（非递归方式）
     */
    public void preOrderIterative() {
        System.out.print("前序遍历（非递归）：");
        if (root == null) {
            System.out.println();
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.data + " ");
            // 先压入右子树，再压入左子树，这样出栈时先访问左子树
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        System.out.println();
    }

    /**
     * 中序遍历（递归方式）
     */
    public void inOrderRecursive() {
        System.out.print("中序遍历（递归）：");
        inOrderRecursive(root);
        System.out.println();
    }

    /**
     * 中序遍历递归辅助方法
     * 
     * @param node 当前结点
     */
    private void inOrderRecursive(TreeNode node) {
        if (node != null) {
            inOrderRecursive(node.left);
            System.out.print(node.data + " ");
            inOrderRecursive(node.right);
        }
    }

    /**
     * 中序遍历（非递归方式）
     */
    public void inOrderIterative() {
        System.out.print("中序遍历（非递归）：");
        if (root == null) {
            System.out.println();
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            // 一直向左走，直到左子树为空
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            // 访问栈顶元素
            current = stack.pop();
            System.out.print(current.data + " ");
            // 转向右子树
            current = current.right;
        }
        System.out.println();
    }

    /**
     * 后序遍历（递归方式）
     */
    public void postOrderRecursive() {
        System.out.print("后序遍历（递归）：");
        postOrderRecursive(root);
        System.out.println();
    }

    /**
     * 后序遍历递归辅助方法
     * 
     * @param node 当前结点
     */
    private void postOrderRecursive(TreeNode node) {
        if (node != null) {
            postOrderRecursive(node.left);
            postOrderRecursive(node.right);
            System.out.print(node.data + " ");
        }
    }

    /**
     * 后序遍历（非递归方式）
     */
    public void postOrderIterative() {
        System.out.print("后序遍历（非递归）：");
        if (root == null) {
            System.out.println();
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> output = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.push(node.data);
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        // 输出栈中的元素
        while (!output.isEmpty()) {
            System.out.print(output.pop() + " ");
        }
        System.out.println();
    }

    /**
     * 层序遍历（辅助方法，用于显示树结构）
     */
    public void levelOrder() {
        System.out.print("层序遍历：");
        if (root == null) {
            System.out.println();
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.data + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        System.out.println();
    }

    /**
     * 获取树的高度
     * 
     * @return 树的高度
     */
    public int getHeight() {
        return getHeightRecursive(root);
    }

    /**
     * 递归计算树的高度
     * 
     * @param node 当前结点
     * @return 子树的高度
     */
    private int getHeightRecursive(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = getHeightRecursive(node.left);
        int rightHeight = getHeightRecursive(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 获取树的结点总数
     * 
     * @return 结点总数
     */
    public int getNodeCount() {
        return getNodeCountRecursive(root);
    }

    /**
     * 递归计算结点总数
     * 
     * @param node 当前结点
     * @return 子树的结点数
     */
    private int getNodeCountRecursive(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + getNodeCountRecursive(node.left) + getNodeCountRecursive(node.right);
    }
}
